package pl.edu.agh.jemo.evolution.selections.impl;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import pl.edu.agh.jemo.evolution.common.JemoRandom;
import pl.edu.agh.jemo.evolution.population.Population;
import pl.edu.agh.jemo.evolution.selections.Tournament;
import pl.edu.agh.jemo.evolution.specimen.Specimen;

/**
 * Implementation of tournament, using binary tournament tree.
 * Tournament works in two stages. First tournament tree is created, then based on this tree, new specimen are chosen. The higher specimen is in tournament tree, the higher is chance for selection.
 * Tournament may choose one specimen multiple times, but then it's copy is created.
 * 
 * @author Jakub Dombrowski, Marcin Zbijowski
 */
public class BinaryTournament extends
		Tournament {

	/**
	 * Performs binary tournament.
	 * First creates tree, on which leaves are all specimen. Leaves are compared in pairs, and winners are placed in parent nodes. This procedure is repeated, until all tree is build, and winner is found.
	 * When tree is created, tournament generates number of levels and walks down the tree randomly this number. It chooses one specimen from chosen level and writes it into output population.
	 * Whole process is repeated, until expected number of specimen is found.
	 * 
	 * @param competitors Population reference containing competing specimen and return population after tournament.
	 */
	@Override
	public void performTournament(
			Population competitors) {
		
		List<BinaryTournamentTree> competitorsList = new ArrayList<BinaryTournamentTree>();
		
		for (Specimen spec : competitors) {
			competitorsList.add(new BinaryTournamentTree(spec));
		}

		Collections.shuffle(competitorsList);

		int treeSize = 1;
	
		while (competitorsList.size() > 1) {
			List<BinaryTournamentTree> newRound = new ArrayList<BinaryTournamentTree>();

			for (int i = 0; i < competitorsList.size(); i += 2) {
				
				BinaryTournamentTree competitor1 = competitorsList.get(i);
				BinaryTournamentTree competitor2 = ( (i + 1) < competitorsList.size() ? competitorsList.get(i+1) : null);
				
				BinaryTournamentTree winner = competitor1;
				if ((i + 1) < competitorsList.size()) {
					if ((competitorsList.get(i+1).getSpecimen().getFitness() < winner.getSpecimen().getFitness())) {
						winner = competitorsList.get(i+1);
					}
				}
				
				winner.setLeft(competitor1);
				winner.setRight(competitor2);
				competitor1.setUp(winner);
				if (competitor2 != null) {
					competitor2.setUp(winner);
				}
				
				newRound.add(winner);
			}
			treeSize++;
			competitorsList = newRound;
		}

		competitors.clear();

		for (int i = 0; i < expectedPopulationSize; i++) {
			int depth = JemoRandom.getRandom().nextInt(treeSize);
			BinaryTournamentTree root = competitorsList.get(0);
			while ((depth > 0) && (root != null) && (root.getLeft() != null)
					&& (root.getRight() != null)) {
				if (JemoRandom.getRandom().nextBoolean() == true) {
					root = root.getLeft();
				} else {
					root = root.getRight();
				}
				depth--;
			}
				
			competitors.add(root.getSpecimen().clone());
		}
	}
}
